package com.origin.niuke.linkedlist;

import general_class.ListNode;

/**
 * NC23 划分链表
 * 算法：链表 + 双指针
 *
 * @author yezh
 * @date 2022/11/22 21:32
 */
public class NC23 {

    public ListNode partition(ListNode head, int x) {
        // write code here
        ListNode a = new ListNode(-1), b = new ListNode(-1);
        ListNode p1 = a, p2 = b;
        while (head != null) {
            if (head.val < x) {
                p1.next = head;
                p1 = p1.next;
            } else {
                p2.next = head;
                p2 = p2.next;
            }
            head = head.next;
        }
        p1.next = b.next;
        p2.next = null;
        return a;
    }

}
